package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_99_恢复二叉搜索树 {
    @Test
    public void main() {

        recoverTree(TreeNode.initRoot());
    }

    /**
    题目：给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

     示例 1：
     输入：root = [1,3,null,null,2]
     输出：[3,1,null,null,2]
     解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

     示例 2：
     输入：root = [3,1,4,null,null,2]
     输出：[2,1,4,null,null,3]
     解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

    分析：【P 💜💜💜】
       1.中序遍历：保证顺序，找出两个错误节点，交换他们的值
            --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
            --时长：20分钟
      大神：定义虚拟头节点：int.min  ，第一个错误节点，第二个错误节点
            --节省了内存开销

    边界值 & 注意点：
       1.
     **/
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        dfs(root,list);
        int i=0;
        for ( ;i < list.size()-1; i++) {
           if(list.get(i).val>list.get(i+1).val)
               break;
        }
        int j=i+1;
        for ( ;j < list.size(); j++) {
            if(list.get(j).val>list.get(i).val)
                break;
        }
        list.get(i).val = list.get(i).val^list.get(--j).val;
        list.get(j).val = list.get(i).val^list.get(j).val;
        list.get(i).val = list.get(i).val^list.get(j).val;
    }

    private void dfs(TreeNode root, List<TreeNode> list) {
        if(root==null)return;
        dfs(root.left,list);
        list.add(root);
        dfs(root.right,list);
    }
}
